package dukeAll;


public class AnotherCoinProblem {
  public int minimumCoin(long cost) {
    int count = 0;
    
    while(cost > 0) {
      count += (int)cost/maxMatch(cost);
      cost = cost%maxMatch(cost);
  }
  return count;
  }

    public long maxMatch(long cost) {
      if(cost < 0) return -1;
      if(cost < 25)
        return (cost < 10)?1:10;
      
      long num_1 = 25;
      long num_2 = 1;
      while(num_1*100 <= cost) num_1 *= 100;
      while(num_2*10 <= cost) num_2 *= 10;

      return Math.max(num_1, num_2);
    }
  }